package Interview;

class LinkedNode{
	int data;
	LinkedNode next;
	public LinkedNode(int data) {
		super();
		this.data = data;
	}
}

public class D2 {

	public static LinkedNode sort(LinkedNode head1,LinkedNode head2){
		if(head1==null&&head2==null){
			return null;
		}
		if(head1==null){
			return head2;
		}
		if(head2==null){
			return head1;
		}
		LinkedNode res = null;
		if(head1.data<head2.data){
			res = head1;
			head1 = head1.next;
		}else{
			res = head2;
			head2 = head2.next;
		}
		LinkedNode current = res;
		while(head1!=null&&head2!=null){
			if(head1.data<head2.data){
				current.next = head1;
				head1 = head1.next;
				current = current.next;
			}else{
				current.next = head2;
				head2 = head2.next;
				current = current.next;
			}
		}
		current.next =( head1==null)?head2:head1;
		return res;
	}
	
	public static void main(String[] args) {
		LinkedNode head1 = new LinkedNode(1);
		LinkedNode head12 = new LinkedNode(21);
		LinkedNode head13 = new LinkedNode(31);
		LinkedNode head14 = new LinkedNode(4111);
		head1.next = head12;
		head12.next = head13;
		head13.next = head14;
		head14.next = null;
		
		LinkedNode head2 = new LinkedNode(5);
		LinkedNode head22 = new LinkedNode(69);
		LinkedNode head23 = new LinkedNode(73);
		LinkedNode head24 = new LinkedNode(83);
		LinkedNode head25 = new LinkedNode(93);
		LinkedNode head26 = new LinkedNode(103);
		LinkedNode head27 = new LinkedNode(11333);
		head2.next = head22;
		head22.next = head23;
		head23.next = head24;
		head24.next = head25;
		head25.next = head26;
		head26.next = head27;
		head27.next = null;	
		LinkedNode res = sort(null, head2);
		while(res!=null){
			System.out.println(res.data);
			res = res.next;
		}
	}
}
